package com.zhj.algorithm.sort;

/**
 * @PackageName:com.zhj.algorithm.sort
 * @ClassName:Insertion
 * @auter: 朱慧杰
 * @date:2020/7/17 0017 9:16
 **/
public class InsertionSort {

    public static void insertSort(Integer[] arr) {

        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < arr[i-1]){
                int temp = arr[i];
                int j;
                for (j = i-1; j >= 0 && arr[j]>temp; j--) {
                    arr[j+1] = arr[j];
                }
                arr[j+1] = temp;
            }
        }
    }

    /**
     * 对数组a中的元素排序  ----插入排序
     * @param a
     */
    public static void sort (Comparable[] a) {

        for (int i = 1; i < a.length; i++) {
            for (int j = i; j >  0; j--) {
                // 比较索引j处的值和索引j-1处的值，如果j-1处的值比索引j处的值大，则交换数据，如果不大，那么会找到合适的位置，退出循环即可
                // 时间复杂度 O(n^2)
                if (greater(a[j-1],a[j])) {
                    exch(a,j-1,j);
                }else {
                    break;
                }
            }
        }

    }

    /**
     * 比较v元素是否大于m元素
     * @param a
     */
    public static boolean greater (Comparable v, Comparable w) {
        return v.compareTo(w)>0;
    }

    /**
     * 数组元素i 和 j 交换位置
     * @param a
     */
    public static void exch (Comparable[] a, int i, int j) {

        Comparable temp;

        temp = a[i];
        a[i] = a[j];
        a[j] = temp;

    }

}
